/****************************************************
  @title: 数据结构实验
  @name: <实验10-2> 排序
  @object:
      [实验目的]
          实现各种排序方法：直接插入排序，折半插入
          排序，起泡排序，快速排序，简单选择排序和
          堆排序。
          观察各种排序算法的排序过程。 
      [实验提示]
          1. 实现InsertSort(a,n)对数组数据a[0..n-1]
             进行直接插入排序。然后，修改算法调用
             PrintArray打印每一趟排序结果，以便观
             察排序过程
          3. 实现BinInsertSort折半插入排序算法，并
             打印每一趟排序结果
          4. 实现BubbleSort起泡排序算法，并打印
             每一趟排序结果
          5. 实现QuickSort快速排序算法，并打印每一
             次分割完成后的结果，观察排序过程 
          6. 实现SelectSort简单选择排序算法，并打印
             每一趟排序结果
          7. 完成堆排序有关的算法
  @include:
  @usage:
      请查看"TO-DO列表",根据要求完成代码
  @copyright: BTC 2004, Zhuang Bo
  @author: Zhuang Bo
  @date: 2004
  @description:
*****************************************************/

#include <stdio.h>
#include <stdlib.h>

//用户数据类型
typedef int T;

//直接插入排序
void InsertSort(T a[],int n);
//折半插入排序
void BinInsertSort(T a[],int n);
//起泡排序
void BubbleSort(T a[],int n);
//快速排序
void QuickSort(T a[],int low,int high);
//简单选择排序
void SelectSort(T a[],int n);
//堆排序
void HeapSort(T a[],int n);

//重新设置测试数据
void ResetData(T a[],int n);
//打印数组数据
void PrintArray(T a[],int low,int high);

int main()
{
    T a[20];
    int n=20;

    //直接插入排序
    printf("\n直接插入排序\n");
    ResetData(a,n);
    PrintArray(a,0,n-1);
    InsertSort(a,n);
    printf("排序结果:\n");
    PrintArray(a,0,n-1);

    //折半插入排序
    printf("\n折半插入排序\n");
    ResetData(a,n);
    PrintArray(a,0,n-1);
    BinInsertSort(a,n);
    printf("排序结果:\n");
    PrintArray(a,0,n-1);

    //起泡排序
    printf("\n起泡排序\n");
    ResetData(a,n);
    PrintArray(a,0,n-1);
    BubbleSort(a,n);
    printf("排序结果:\n");
    PrintArray(a,0,n-1);

    //快速排序
    printf("\n快速排序\n");
    ResetData(a,n);
    PrintArray(a,0,n-1);
    QuickSort(a,0,n-1);
    printf("排序结果:\n");
    PrintArray(a,0,n-1);

    //简单选择排序
    printf("\n简单选择排序\n");
    ResetData(a,n);
    PrintArray(a,0,n-1);
    SelectSort(a,n);
    printf("排序结果:\n");
    PrintArray(a,0,n-1);

    //堆排序
    printf("\n堆排序\n");
    ResetData(a,n);
    PrintArray(a,0,n-1);
    HeapSort(a,n);
    printf("排序结果:\n");
    PrintArray(a,0,n-1);
    
    system("pause");
    return 0;
}


//直接插入排序
void InsertSort(T a[],int n)
{
    // TODO (#1#): 对a[0..n-1]进行直接插入排序 
    
    //-------------------------------------
}

//折半插入排序
void BinInsertSort(T a[],int n)
{
    // TODO (#1#): 对a[0..n-1]进行折半插入排序 
    
    //-------------------------------------
}

//起泡排序
void BubbleSort(T a[],int n)
{
    // TODO (#1#): 对a[0..n-1]进行起泡排序 
    
    //-------------------------------------
}

//快速排序
void QuickSort(T a[],int low,int high)
{
    // TODO (#1#): 对a[0..n-1]进行快速排序 
    
    //选择枢轴
    
    //分割
    
    //分别对两部分记录进行快排
    
    //-------------------------------------
}

//简单选择排序
void SelectSort(T a[],int n)
{
    // TODO (#1#): 对a[0..n-1]进行简单选择排序 
    
    //-------------------------------------
}

//筛选成堆
//  a[s..m]除a[s]外满足堆的定义
//  现调整a[s..m]成大顶堆
//  与课本稍微不同,数据在a[0..n-1]
void HeapAdjust(T r[],int s,int m)
{
    // TODO (#1#): 把a[s..m]调整成大顶堆 
    
    //-------------------------------------
    /*** 参考代码 
    int j;
    T rc;

    rc = r[s];
    for(j=2*s+1; j<=m; j=2*j+1) {
        if(j<m &&r[j]<r[j+1]) j++;
        if(rc>=r[j]) break;
        r[s] = r[j];
        s = j;
    }
    r[s] = rc;
    ***/
}

//堆排序
//  与课本稍微不同a[0..n-1]为堆
void HeapSort(T a[],int n)
{
    // TODO (#1#): 对a[0..n-1]进行堆排序
    
    //-------------------------------------
    /*** 参考代码 
    int i;
    T t;

    for( i=(n-2)/2; i>=0; i--)
        HeapAdjust(a,i,n-1);
    PrintArray(a,0,n-1); //建立堆
    for(i=n-1; i>0; i--) {
        t=a[0]; a[0]=a[i]; a[i]=t;
        HeapAdjust(a,0,i-1);
        PrintArray(a,0,i);
    }
    ***/
}

//重新设置测试数据
//  以便使用相同的测试数据
void ResetData(T a[],int n)
{
    //测试数据
    static T data[20]={
        49,38,65,97,76,13,27,49,55,10,
        87,70,91,33,69,81,22,56,28,39
    };
    int i;
    for(i=0; i<n; i++)
        a[i]=data[i];
}

//打印数组数据
// 下标从 low 到 high 的数据
void PrintArray(T a[],int low,int high)
{
    int i;
    for(i=0; i<low; i++)
        printf("   "); //略过a[0..low]
    //打印a[low .. high]
    for(i=low; i<=high; i++)
        printf("%3d",a[i]);
    printf("\n");
}

